/*
https://leetcode.cn/problems/exam-room/description/
855. 考场就座
*/

class ExamRoom {
public:
    set<int> num;
    int n=0;
    ExamRoom(int n) {
        this->n=n;
    }
    
    int seat() {
        if(num.size()==0){//题目要求无人的时候插入位置0
            num.insert(0);
            return 0;
        }
        int l=-1,r=0,max=0,insertNum=0; //初始化左右节点，最大距离和要插入的值
        if(*num.begin()!=0)max=*num.begin();//判断0不存在的时候，插入零是否合适
        for(auto i=num.begin();i!=num.end();i++){
            r=*i;
            if(max<(r-l)/2){ //判断插入目前两个节点中间是否合适
                max=(r-l)/2;
                insertNum=l+(r-l)/2;
            }
            l=r;
        }
        if(r!=n-1){//判断n-1不存在的时候，插入n-1是否合适
            if(max<n-1-r)insertNum=n-1;
        }
        num.insert(insertNum);
        return insertNum;
    } 
    void leave(int p) {
        num.erase(p);
    }
};
